package sort

/**
 * 排序算法	平均时间复杂度
 * 冒泡排序	O(n2)
 *
 * 1、基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。
 * 2、过程：
 *      比较相邻的两个数据，如果第二个数小，就交换位置。
 *      从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
 *      继续重复上述过程，依次将第2.3...n-1个最小数排好位置。
 *
 * @Link https://www.jianshu.com/p/ae97c3ceea8d
 */
fun main(args: Array<String>) {

    bubbleSortOptimize(getEsayItems())
}

/**
 * 冒泡排序
 * 缺点：如果当原数组的顺序比较顺的时候，会出现冗余遍历
 */
fun bubbleSort(args: ArrayList<Int>) {
    for (i in 0 until args.size - 1) {
        println("第${i}次：$args")
        var temp: Int
        for (j in args.size - 1 downTo i + 1) {
            if (args[j] < args[j - 1]) {
                //交换较小数
                temp = args[j]
                args[j] = args[j - 1]
                args[j - 1] = temp
            }
        }
    }
    print("最x终：$args")
}

/**
 * 冒泡排序（优化）
 * 当遍历时添加标记，出现顺序改动，则改变标记，
 * 判断标记未变化则说明已排序完成，则退出排序
 */
fun bubbleSortOptimize(args: ArrayList<Int>) {
    var temp: Int//临时变量
    var falg: Boolean//排序变化标记
    for (i in args.indices) {//遍历集合
        println("优化 第${i}次：$args")
        falg = false
        for (j in args.size - 1 downTo i + 1) {//遍历相邻两个数大小，从后向前遍历
            if (args[j] < args[j - 1]) {
                falg = true
                temp = args[j]
                args[j] = args[j - 1]
                args[j - 1] = temp
            }
        }
        if (!falg) {
            break
        }
    }
    print("优化 最x终：$args")
}

fun getEsayItems(): ArrayList<Int> {
    return arrayListOf(13, 14, 17, 7, 28, 11, 23, 15)
}

fun getItems(): ArrayList<Int> {
    return arrayListOf(42, 20, 17, 13, 28, 14, 23, 15)
}